
import com.sun.deploy.util.ArrayUtil;

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Solution solution =new Solution();
        solution._recurrence(0,6,"");

        int i = climbStairs(45);
        System.out.println(i);
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        queue.add(null);
        queue.add(null);
        System.out.println(queue.size());
        queue.poll();
        System.out.println(queue.isEmpty());
    }

    public List<String> generateParenthesis(int n) {
        _recurrence(0,2*n,"");
        return null;
    }

    private void _recurrence(int i, int n, String s) {
        if(i>=n){
            System.out.println(s);
            return;
        }
        _recurrence(i+1,n,s+"(");
        _recurrence(i+1,n,s+")");
    }

    public static int climbStairs(int n) {
        //递归的方法
        //1.递归的终止条件
        int s = 0;
        if(n == 1){
            return 1;
        }
        if(n==2)return 2;

//        2.当前层的操作
        s=climbStairs(n-1)+climbStairs(n-2);
//        3.调用递归方法
//        4.清除成员变量
        return s;
    }


    public static List<List<Integer>> levelOrder(Node root) {
        //无法采用递归的形式去输出，递归的遍历是以根节点和子节点进行遍历的，无法进行分层去记录信息
        // 可以采用队列的形式将每一层所有的节点都放进队列中，在对队列进行操作的时候，同时将队列中的每一个元素的子节点依次放入队列中，由于是先进先出的特性，可以将每一层的数据完美分割开来
        List<Node> nodes = Arrays.asList(root);
        //申请一个队列
        Queue<Node> queue = new LinkedList<>();//双端队列
        queue.add(root);
        List<List<Integer>> lists = new ArrayList<>();
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for(int k=0;k<size;k++){
                Node poll = queue.poll();
                list.add(poll.val);
                List<Node> children = poll.children;
                if(children !=null) {
                    for (Node node : children) {
                        queue.add(node);
                    }
                }
            }
            lists.add(list);
        }
        return lists;
    }

    static List<Integer> list= new ArrayList<>();
    public static List<Integer> preorder(Node root) {
        //前序遍历中左右
        if(root ==null){
            return list;
        }
        List<Node> childrenList = root.children;
        list.add(root.val);
            for(Node node :childrenList){
                preorder(node);
            }
        return list;
    }

    public static List<List<String>> groupAnagrams(String[] strs) {
        // 使用hash表结构进行存储anagrams
        Map<String,List<String>> map = new HashMap<>();
        for(String s:strs){
            //定义hash函数确定annagrams的key
            char[] chars = s.toCharArray();
            String.copyValueOf(chars);
            int[] count = new int[26];
            StringBuffer sb = new StringBuffer();
            for (char c:chars){
                count[c-'a']++;
            }
            for(int i=0;i<count.length;i++){
                sb.append(count[i]);
            }
            String key = sb.toString();
            if(map.containsKey(key)){
                List<String> list = map.get(key);
                list.add(s);
            }else{
                List<String> list = new ArrayList<>();
                list.add(s);
                map.put(key,list);
            }
        }
        //将map转为List
        return new ArrayList<>(map.values());
    }


    public static boolean isAnagram(String s, String t) {
//        char[] chars = s.toCharArray();
//        char[] chars1 = t.toCharArray();
//        Arrays.sort(chars);
//        Arrays.sort(chars1);
//        return Arrays.equals(chars,chars1);
        int[] count = new int[26];
        for(int i=0;i<s.length();i++){
            count[s.charAt(i)-'a']++;
            count[t.charAt(i)-'a']--;
        }
        for(int i =0;i<count.length;i++){
            if(count[i] !=0){
                return false;
            }
        }
        return true;
    }


    public static int trap(int[] height) {
        // 采用栈结构进行计算，针对于每一根柱子，找出左右边界，算出当前柱子能够成多少水
        Stack<Integer> stack = new Stack<>();
        int area = 0;
        for(int i=0;i<height.length;i++){
            while(!stack.empty() && height[stack.peek()]<height[i]){
                int pop = stack.pop();
                if(stack.empty()){
                    break;
                }
                area = area +(i-stack.peek()-1)*(Math.min(height[i],height[stack.peek()])-height[pop]);
            }
            stack.push(i);
        }
        return area;
    }

    public static void cleanDeque(ArrayDeque<Integer> deque,int[] nums,int j,int k){
        if(!deque.isEmpty()&&deque.getFirst() == (j-k)){
            deque.removeFirst();
        }

        if(deque.isEmpty()){
            deque.addFirst(j);
        }else{
            while(!deque.isEmpty()&&nums[deque.getLast()]<nums[j]){
                deque.removeLast();
            }
            deque.addLast(j);
        }
    }
    public static int[] maxSlidingWindow(int[] nums, int k) {
        //采用双向队列Deque，可以将窗口中最大值储存在队列最左端
        int[] maxNums = new int[nums.length-k+1];
        ArrayDeque<Integer> deque = new ArrayDeque();
        //初始化deque队列
        for(int i=0;i<k;i++){
            cleanDeque(deque,nums,i,k);
        }
        maxNums[0] = nums[deque.getFirst()];
        for(int i =k;i<nums.length;i++){
            cleanDeque(deque,nums,i,k);
            maxNums[i-k+1] = nums[deque.getFirst()];
        }
        return maxNums;
    }
}




